/*
 * @lc app=leetcode.cn id=2104 lang=cpp
 *
 * [2104] 子数组范围和
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        //!暴力法
        // int n = nums.size();
        // long long ret = 0;
        // for (int i = 0; i < n; i++) {
        //     int minVal = INT_MAX, maxVal = INT_MIN;
        //     for (int j = i; j < n; j++) {
        //         minVal = min(minVal, nums[j]);
        //         maxVal = max(maxVal, nums[j]);
        //         ret += maxVal - minVal;
        //     }
        // }
        // return ret;

        //!单调栈
        //范围和sum 等于所有子数组的最大值之和 减去所有子数组最小值之和
        int n = nums.size();
        auto ms = [&](auto&& cmp){
            vector<long long> cc(n, 1);
            stack<int> s;
            s.push(0);
            for(int i = 1; i < n; ++i){
                while(s.size() && !cmp(nums[s.top()], nums[i])){
                    cc[s.top()] *= i - s.top();
                    s.pop();
                }
                cc[i] *= s.empty() ? i + 1 : i - s.top();
                s.push(i);
            }
            while(s.size()){
                cc[s.top()] *= n - s.top();
                s.pop();
            }
            return inner_product(begin(nums), end(nums), begin(cc), 0LL);
        };
        return ms(greater()) - ms(less());
    }
};
// @lc code=end

